class LNode {
  prev: LNode | null;
  next: LNode | null;
  key: number;
  value: number;
  constructor(
    key: number = Number.MIN_SAFE_INTEGER,
    value: number = Number.MIN_SAFE_INTEGER,
    prev: LNode | null = null,
    next: LNode | null = null
  ) {
    this.key = key;
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}
/**
 * https://leetcode-cn.com/problems/lru-cache/
 * LRU缓存机制
 */
class LRUCache {
  private capacity = 0;
  private sizes = 0;
  private head: LNode;
  private tail: LNode;
  private cache: Record<number, LNode> = {}; // 缓存key和LNode的
  constructor(capacity: number = 2) {
    // 默认容量是2
    // 初始化链表
    this.capacity = capacity;

    // 初始化虚拟头尾节点
    this.head = new LNode();
    this.tail = new LNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * 取出key对应的值
   * @param key
   */
  get(key: number) {
    const n = this.cache[key];
    if (n == null) {
      return -1; // 还没有存储
    }

    // 1. 将该节点移动到头部
    this.moveToHead(n);

    // 2. 返回
    return n.value;
  }

  /**
   * 放入缓存中
   * @param key
   * @param value
   */
  put(key: number, value: number) {
    const exist = this.cache[key];
    if (exist) {
      // 修改value
      exist.value = value;

      // 移动到头部
      this.moveToHead(exist);
    } else {
      // 新增的

      const newNode = new LNode(key, value);
      // 添加到头部
      this.addToHead(newNode);

      // 长度加1
      this.sizes++; 

      // 添加到缓存中
      this.cache[key] = newNode

      // 如果容量超过了
      if (this.sizes > this.capacity) {
        // 删掉尾巴
        const tail = this.removeTail();

        // 清除缓存
        delete this.cache[tail.key]

        // 长度减1
        this.sizes--
      }

    }
  }

  /**
   * 删除掉尾巴
   */
  private removeTail() {
    const tail = this.tail.prev!;
    this.removeNode(tail)
    return tail
  }

  /**
   * 添加节点到头部
   * @param node
   */
  private addToHead(node: LNode) {
    const head = this.head;

    // 修改node的指向
    node.prev = head;
    node.next = head.next;

    // 修改原来的head的指向
    head.next!.prev = node;
    head.next = node;
  }

  /**
   * 删除节点
   * @param node
   */
  private removeNode(node: LNode) {
    const prev = node.prev!;
    const next = node.next!;
    prev.next = next;
    next.prev = prev;
  }

  /**
   * 移动节点到头部
   * @param node
   */
  private moveToHead(node: LNode) {
    this.removeNode(node); // 先删除该节点
    this.addToHead(node); // 移动节点
  }
}

const lru = new LRUCache(2);

lru.put(2, 1);
lru.put(2, 2);
// console.log(lru.keyToNode);

// lru.put(1, 1);
// lru.put(2, 2);
// console.log(lru.get(1));
// lru.put(3, 3);
// console.log(lru.get(2));
// lru.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// console.log(lru.get(1)); // 返回 -1 (未找到)
// console.log(lru.get(3)); // 返回 3
// console.log(lru.get(4)); // 返回 4
